package org.dlsu.mt.parser.generator;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Enumeration;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Vector;


/**
 * A generic GLR parser generator created for LFG. To generate the parse table, provide the grammar
 * inside a text file and instantiate the parser generator with the filename like so:
 *		GLRParserGenerator pg = new	GLRParserGenerator("my_grammar.txt");
 * After instantiation call the createParseTable() method to generate an instance of ParseTable
 * representing your parse table generated based on the grammar. All the symbols inside the input grammar
 * are all case insensitive. And a reserved symbol (**EMPTY**) is for the empty symbol.
 * The parser generator currently does not handle productions with the empty symbol
 * together with non-empty symbols inside a rule(e.g. A = **EMPTY** B C, A = A **EMPTY** B, A = A B **EMPTY**).
 * The only time it allows the placement of the empty symbol on the right hand side of the production
 * is when it is only deriving empty (e.g. A = **EMPTY**).
 * The format of the text file is as follows:
 * <hr>
 * <PRE>
 * Terminals:
 * <terminal 1>
 * <terminal 2>
 * <terminal 3>
 * ...
 * <terminal n>
 * NonTerminals:
 * <non-terminal 1>
 * <non-terminal 2>
 * <non-terminal 3>
 * ...
 * <non-terminal n>
 * Start:
 * <start symbol>
 * Rules:
 * <rule 1>
 * <rule 2>
 * <rule 3>
 * ...
 * <rule n>
 * **END**
 * </PRE>
 * <hr>
 * The symbols defining a rule are all separated by spaces. The format of the rule is as follows:
 * <hr>
 * <PRE>
 * <Left Hand Side> = <Right Hand Side symbol 1> [<space> *[<feature 1>]* ] <space> <Right Hand Side symbol 2> [<space> *[<feature 2>]* ] <space> .... <space> <Right Hand Side symbol n> [<space> *[<feature n>]* ]
 * </PRE>
 * <hr>
 * This is how to specify the ambigious expressions grammar for this parser generator:
 * <hr> <PRE>
 * Terminals:
 * id
 * +
 * *
 * (
 * )
 * NonTerminals:
 * E
 * Start:
 * E
 * Rules:
 * E = E + E
 * E = E * E
 * E = id
 * **END**
 * </PRE> <hr>
 */
public class GLRParserGenerator {

	/** The reader for the file to open. */
	protected BufferedReader input;
	/** The delimiters used by the Parser Generator*/
	protected String delims = " \n\r=";
	/** The set of terminals read and used by the generator */
	protected HashSet t= new HashSet();
	/** The set of non-terminals read and used by the generator */
	protected HashSet nt= new HashSet();

	/** The list of rules that has been generated by the generator */
	protected Vector rules = new Vector(20);
	/** The integer mapping of the sets of items */
	protected Hashtable setMapping = new Hashtable();
	/** The integer set mapping of the rules where the dot is at the rightmost end */
	protected Hashtable ruleEndMapping = new Hashtable();
	/** The set of nullable symbols */
	protected HashSet nullableSymbols = new HashSet();
	/** A hashtable containing the FIRST(X) set of a non-terminal X*/
	protected Hashtable firstSet = new Hashtable();
	/** A hashtable containing the FOLLOW(X) set of a non-terminal X */
	protected Hashtable followSet = new Hashtable();
	/** The start symbol for the given grammar */
	protected String startSymbol="";
	/** The new start symbol by augmenting the grammar */
	protected String newStartSymbol="";
	/** The containing all the goto sets*/
	protected Vector gotoTable = new Vector();
	/** The initial state of for the generated parser table */
	public static final int INITIALSTATE = 0;
	private final String EMPTY = ParseTable.EMPTY; // The empty symbol
	private final String ENDMARKER = ParseTable.ENDMARKER; // The end marker
	/** The end of line character or marker */
	public static String ENDLINE = "\r";

	/**
	 * Instantiate a GLR Parser
	 * @param filename Filename of the grammar
	 */
	public GLRParserGenerator(String filename) throws Exception {
		input = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
	}

	/**
	 * Initializes the list of terminals, non-terminals, and the rules
	 */
	protected void init() throws Exception{
		String s, term, feature;
		boolean prevTerm=false;
		Rule r=null;
// Looks for keyword 'Terminals:'
		while(!(s=nextToken()).equalsIgnoreCase("Terminals:"));
// Initializes list of terminals
		while(!(s=nextToken()).equalsIgnoreCase("NonTerminals:")){
			if( !isDelim( (s).charAt(0) ) ) {
				t.add(s.toUpperCase());
			}
		}
// Initializes list of non-terminals
		while(!(s=nextToken()).equalsIgnoreCase("Start:")) {
			if( s.length()>0)
				if (!isDelim(s.charAt(0))) {
					nt.add(s.toUpperCase());
					firstSet.put(s.toUpperCase(), new HashSet());
					followSet.put(s.toUpperCase(), new HashSet());
				}
		}
// Initializes start symbol
		while(!(s=nextToken()).equalsIgnoreCase("Rules:")) {
			if( s.length()>0)
				if (!isDelim(s.charAt(0)))
					nt.add( newStartSymbol= ((startSymbol=s.toUpperCase())+"'") );
		}
// Initializes list of rules
		while(!(s=nextToken()).equalsIgnoreCase("**END**")){
			if( s.length()>0) {
				if (!isDelim(s.charAt(0))) {
					if ( !hasNonTerminal(s) )
						throw new RuntimeException("Symbol is not defined as a Non-Terminal: " + s);
					rules.add( (r=new Rule(s.toUpperCase())) );
					while( !(s=nextToken()).equals("=") );
					while( !(s=nextToken()).equals(ENDLINE)) {
						if( s.length()>0) {
							if (!isDelim(s.charAt(0)))
								if(s.startsWith("*[")) {
									if (!prevTerm)
										throw new RuntimeException("Grammar rules is not for LFG: " + r.toString() + " " +s);
									else
										r.addRHSFeature(s.substring(2,s.length()-2));
									prevTerm = false;
								} else if ( hasTerminal(s) || hasNonTerminal(s) || s.equalsIgnoreCase(EMPTY)){
									if (prevTerm)
										r.addRHSFeature("");
									r.addRHSTerm(s.toUpperCase());
									prevTerm = true;
								} else {
									throw new RuntimeException("Symbol is not defined: " + s);
								}
						}
					}

					if (r.getRHSTermSize() > r.getFeatureSize())
						r.addRHSFeature("");
					prevTerm=false;
				}
			}
		}
// Add the empty symbol as a nullable symbol
		nullableSymbols.add(EMPTY);
		t.add(ENDMARKER);

		closeInput();
	}

	/** Gets the list of rules associated with the left-hand side symbol
		@param lhs Left-hand side string*/
	protected Vector getRules(String lhs) {
		Iterator i = rules.iterator();
		Vector v = new Vector();
		Rule r;

		while(i.hasNext()) {
			r = (Rule) i.next();
			if(r.isLHSEqual(lhs))
				v.addElement(r);
		}

		return v;
	}

	/** Checks whether the LHS symbol is in the given set
		@param hs Hashset to search on
		@param lhs Left-hand side string*/
	protected boolean isLHSInSet(HashSet hs, String lhs) {
		Iterator i = hs.iterator();
		Rule r;

		while(i.hasNext()) {
			r = (Rule) i.next();
			if(r.isLHSEqual(lhs)) {
				return true;
			}
		}

		return false;
	}

	/**
	 * Gets the closure of the set
	 */
	protected void closure(HashSet s) {
		Vector v = null;
		HashSet toAdd = new HashSet();
		HashSet toCheck,added = new HashSet();
		HashSet checked = new HashSet();
		Iterator i;
		Rule r;
		String term;
		int ctr;

		toCheck = (HashSet) s.clone();
// Add an element to "toAdd" for the loop to begin
		do {
// Clears the list of lhs to add
			toAdd.clear();
// Checks the list and adds all the non-terminal symbol rules or production
// to the right of dot of each production to the "toAdd" set
			i = toCheck.iterator();
			while(i.hasNext()) {
				r = (Rule) i.next();
				term = r.getRightOfDot();
				checked.add(r);
				if (term == null) continue;
				if ( !added.contains(term) && hasNonTerminal(term) ) {
					toAdd.add(term);
					added.add(term);
				}
			}
			toCheck.clear();
// Adds the contents of the set "toAdd" to the closure of the set
			i = toAdd.iterator();
			while(i.hasNext()) {
				term = (String) i.next();
				v = getRules(term);
				for(ctr=0;ctr<v.size();ctr++)
					toCheck.add(v.elementAt(ctr));
			}
		} while(!toAdd.isEmpty());

		i = checked.iterator();
		while(i.hasNext())
			s.add(i.next());
	}

	/** Creates the goto set for GOTO(hs, s)
	 *
	 * @param hs The source set unto which GOTO will be computed
	 * @param s The symbol to goto
	 * @return The goto set of the set <i>hs</i> given the symbol <i>s</i>
	 */
	protected HashSet createGoto(HashSet hs, String s) {
		Iterator i = hs.iterator();
		HashSet gotoSet = new HashSet();
		String term = null;
		Rule r;

		while(i.hasNext()) {
			r = (Rule) i.next();
			term = r.getRightOfDot();
			if (term == null || term.equalsIgnoreCase(EMPTY)) continue;
			if( term.toUpperCase().equalsIgnoreCase(s.toUpperCase()) )
				gotoSet.add(r.moveDot());
		}
		closure(gotoSet);
		return gotoSet;
	}

	/**
	 * Creates the collection of sets
	 */
	protected void createSets() {
// Augment a new start symbol to the grammar
		Iterator i,i2;
		Rule r;
		HashSet setOfItems = new HashSet();
		HashSet hs = new HashSet();
		HashSet terms = new HashSet();
		HashSet computed = new HashSet();
		HashSet hsTemp, gotoSet;
		HashSet setClone;
		Vector v;
		boolean change=false;
		String term;
		int setCtr=INITIALSTATE;
		int gotoIndex;

		r = new Rule(newStartSymbol);
		r.addRHS(startSymbol,"");
		rules.add(r);
		hs.add(r);
		firstSet.put(newStartSymbol,new HashSet());
		followSet.put(newStartSymbol,new HashSet());

// Takes the closure of the initial set and add it to the set of items
		closure(hs);
		setOfItems.add(hs);
		setMapping.put(hs,new Integer(setCtr++));
		gotoTable.add(new Hashtable());
// Build the Set of Items
		do {
			change =false;
			i = setOfItems.iterator();
			setClone = (HashSet) setOfItems.clone();
			while(i.hasNext()) {
				hsTemp = (HashSet) i.next();
				if (!computed.contains(hsTemp)) {
					gotoIndex = ((Integer) setMapping.get(hsTemp)).intValue();
					computed.add(hsTemp);
					i2 = hsTemp.iterator();
					while(i2.hasNext()) {
						r = (Rule) i2.next();
						term = r.getRightOfDot();
						if (term == null || term.equalsIgnoreCase(EMPTY)) {
							v = (Vector) ruleEndMapping.get(r);
							if (v==null) {
								v = new Vector();
								ruleEndMapping.put(r, v);
							}
							v.add(setMapping.get(hsTemp));
							continue;
						}
						terms.add(term);
					}
					i2=terms.iterator();
					while(i2.hasNext()) {
						term = (String) i2.next();
						gotoSet = createGoto(hsTemp,term);
						if (!gotoSet.isEmpty()) {
							if (!setClone.contains(gotoSet)) {
								setMapping.put(gotoSet, new Integer(setCtr++));
								setClone.add(gotoSet);
								gotoTable.add(new Hashtable());
							}
							((Hashtable) gotoTable.elementAt(gotoIndex)).put(term,setMapping.get(gotoSet));
							change = true;
						}
					}
				}
			}
			setOfItems = setClone;
		} while(change);
	}

	//

	/**
	 * Determines whether the grammar symbols are nullable or not
	 */
	protected void computeNullable() {
		Iterator i = nt.iterator();
		Vector v;
		Rule r;
		String term;
		boolean changed=true;
		boolean nullable, ruleNullable;

		while(i.hasNext()) {
			term = (String) i.next();
			v = getRules(term);
			for(int ctr=0;ctr<v.size();ctr++) {
				r = (Rule) v.elementAt(ctr);
				if (r.getRHSTerm(0).equalsIgnoreCase(EMPTY)) {
					nullableSymbols.add(term);
					break;
				}
			}
		}

		while(changed) {
			changed = false;
			i = nt.iterator();
			while(i.hasNext()) {
				term = (String) i.next();
				nullable = false;
				if (!nullableSymbols.contains(term)) {
					v = getRules(term);
					for(int ctr=0;ctr<v.size();ctr++) {
						r = (Rule) v.elementAt(ctr);
						ruleNullable = true;
						for(int j=0;j<r.getRHSTermSize();j++)
							if (!nullableSymbols.contains(r.getRHSTerm(j)))
								ruleNullable=false;
						nullable = nullable || ruleNullable;
					}
					if (nullable) {
						nullableSymbols.add(term);
						changed = true;
					}
				}
			}
		}
	}

	/**
	 * Computes the FIRST of every non-terminal symbol
	 */
	protected void computeFirst() {
		Iterator i = nt.iterator(),j;
		HashSet toCompute = new HashSet();
		HashSet contents,hsTemp;
		String term,symbol;
		Vector v;
		Rule r;
		int prevSize;

		while(i.hasNext()) {
			term = (String) i.next();
			contents = (HashSet) firstSet.get(term);
			if (nullableSymbols.contains(term))
				contents.add(EMPTY);
			v = getRules(term);
			for(int ctr=0;ctr<v.size();ctr++) {
				r = (Rule) v.elementAt(ctr);
				for(int k=0;k<r.getRHSTermSize();k++){
					if (!r.getRHSTerm(k).equalsIgnoreCase(EMPTY) )
						contents.add(r.getRHSTerm(k));
					if (hasNonTerminal(r.getRHSTerm(k)) && nullableSymbols.contains(r.getRHSTerm(k)))
						continue;
					else
						break;
				}
			}
		}

		i = nt.iterator();
		while(i.hasNext()) {
			term = (String) i.next();
			contents = (HashSet) firstSet.get(term);
			do {
				hsTemp = (HashSet) contents.clone();
				j = contents.iterator();
				prevSize = contents.size();

				while(j.hasNext()) {
					symbol = (String) j.next();
					if (hasNonTerminal(symbol)) {
						hsTemp.addAll((HashSet) firstSet.get(symbol));
					}
				}
				contents = hsTemp;
			}while (prevSize != contents.size());

			hsTemp = (HashSet) contents.clone();
			j=contents.iterator();
			while(j.hasNext()) {
				symbol = (String) j.next();
				if(hasNonTerminal(symbol))
					hsTemp.remove(symbol);
			}
			contents = hsTemp;
			firstSet.put(term, contents);
		}
	}

	/**
	 * Closes the input file
	 */
	public void closeInput() throws IOException{
		input.close();
	}

	/**
	 * Computes the FOLLOW of every non-terminal symbol
	 */
	protected void computeFollow() {
		Iterator i = nt.iterator(),j;
		HashSet toCompute = new HashSet();
		HashSet contents,hsTemp;
		String term,symbol,lhs,rhs;
		Vector v;
		Rule r;
		int l;
		int prevSize;

		((HashSet) followSet.get(newStartSymbol)).add(ENDMARKER);

		for(int ctr=0;ctr<rules.size();ctr++) {
			r = (Rule) rules.elementAt(ctr);
			lhs = r.getLHS();
			for(int k=0;k<r.getRHSTermSize();k++){
				rhs = r.getRHSTerm(k);
				contents = (HashSet) followSet.get(rhs);
				if (hasNonTerminal(rhs)) {
					for(l=k+1;l<r.getRHSTermSize();l++) {
						if (!r.getRHSTerm(l).equalsIgnoreCase(EMPTY))
							if (hasNonTerminal(r.getRHSTerm(l)))
								contents.addAll((HashSet) firstSet.get(r.getRHSTerm(l)));
							else
								contents.add(r.getRHSTerm(l));
						if (hasNonTerminal(r.getRHSTerm(l)) && nullableSymbols.contains(r.getRHSTerm(l)))
							continue;
						else
							break;
					}
					if (l == r.getRHSTermSize())
						if (hasNonTerminal(r.getRHSTerm(k)))
							contents.add(lhs);
				}
			}
		}

		i = nt.iterator();
		while(i.hasNext()) {
			term = (String) i.next();
			contents = (HashSet) followSet.get(term);
			do {
				hsTemp = (HashSet) contents.clone();
				j = contents.iterator();
				prevSize = contents.size();

				while(j.hasNext()) {
					symbol = (String) j.next();
					if (hasNonTerminal(symbol)) {
						hsTemp.addAll((HashSet) followSet.get(symbol));
					}
				}
				contents = hsTemp;
			}while (prevSize != contents.size());

			hsTemp = (HashSet) contents.clone();
			j=contents.iterator();
			while(j.hasNext()) {
				symbol = (String) j.next();
				if(hasNonTerminal(symbol) || symbol.equalsIgnoreCase(EMPTY))
					hsTemp.remove(symbol);
			}
			contents = hsTemp;
			followSet.put(term, contents);
		}
	}

	/** Creates the parse table entries
	 *
	 * @param p Parse table to place entries
	 */
	protected void createTableEntries(ParseTable p) {
		Enumeration e = gotoTable.elements(),e2;
		Iterator iter;
		int i=0,index;
		Hashtable terms;
		String term;
		Vector v;
		HashSet follow;
		Rule r;

// Adds the reduce shift and goto actions
		while(e.hasMoreElements()) {
			terms = (Hashtable) e.nextElement();
			e2 = terms.keys();
			while(e2.hasMoreElements()) {
				term = (String) e2.nextElement();
				if (hasTerminal(term)) {
					p.addEntry(i,term,new ParseTableEntry("shift", ((Integer) terms.get(term)).intValue(), null));
				} else if(hasNonTerminal(term)) {
					p.addEntry(i,term,new ParseTableEntry("goto", ((Integer) terms.get(term)).intValue(), null));
				}
			}
			i++;
		}
// Adds the reduce actions
		e = ruleEndMapping.keys();
		while(e.hasMoreElements()) {
			r = (Rule) e.nextElement();
			v = (Vector) ruleEndMapping.get(r);
			if (!r.getLHS().equalsIgnoreCase(newStartSymbol)) {
				follow = (HashSet) followSet.get(r.getLHS());
				for(i=0;i<v.size();i++) {
					index = ((Integer) v.elementAt(i)).intValue();
					iter = follow.iterator();
					while(iter.hasNext())
						p.addEntry(index, (String) iter.next(), new ParseTableEntry("reduce", -1, r));
				}
			} else {
// Adds the initial state to accept
				for(i=0;i<v.size();i++) {
					index = ((Integer) v.elementAt(i)).intValue();
					p.addEntry( index,ENDMARKER, new ParseTableEntry("accept",-1,null));
				}
			}
		}
// Adds errors to the parser table
		for(i=0;i<setMapping.size();i++) {
			iter = t.iterator();
			while(iter.hasNext()) {
				term = (String) iter.next();
				if (p.getEntry(i,term).size() ==0)
					p.addEntry(i,term,new ParseTableEntry("error",-1,null));
			}
			iter = nt.iterator();
			while(iter.hasNext()) {
				term = (String) iter.next();
				if (p.getEntry(i,term).size() ==0)
					p.addEntry(i,term,new ParseTableEntry("error",-1,null));
			}
		}
	}

	/**
	 * Creates the parsetable
	 */
	public ParseTable createParseTable() throws Exception{
		ParseTable p;

		init();
		createSets();
		computeNullable();
		computeFirst();
		computeFollow();
		createTableEntries( (p=new ParseTable(t,nt,rules,setMapping.size(),newStartSymbol,INITIALSTATE)) );
		return p;
	}

	/**
	 * Gets the next token from the file
	 *
	 * @return The next symbol read from the file
	 */
	public String nextToken() throws Exception{
		int c;
		boolean inside=false;
		StringBuffer s = new StringBuffer(10);
		while( (c=input.read()) != -1)
			if (!isDelim((char) c)) {
				s.append((char) c);
				input.mark(1);
				if ((char) c == '*') {
					c=input.read();
					if ((char) c == '[') {
						s.append((char) c);
						inside = true;
						while(inside) {
							while( (char) (c=input.read()) != ']') {
								if((char) c == '\r') {
									throw new RuntimeException("Invalid lexical unit: " + s.toString());
								}
								s.append((char) c);
							}
							s.append((char) c);
							if( (char) (c=input.read()) == '*')
								inside =false;
							s.append((char) c);
							input.mark(1);
						}
					} else input.reset();
				}
			}
			else {
				if (s.length() == 0)
					return ""+(char) c;
				input.reset();
				break;
			}
		return s.toString();
	}

	/**
	 * Gets the remaining string in the line from the file and moves the cursor pointer to the
	 * to the next line
	 *
	 * @return The remaining string in the current line
	 */
	public String nextLine() throws Exception{
		return input.readLine();
	}

	/**
	 * Displays the list of terminals
	 */
	public void printTerminalList() {
		Iterator i = t.iterator();

		while(i.hasNext())
			System.out.println( (String) i.next());
	}

	/**
	 * Displays the list of non-terminals
	 */
	public void printNonTerminalList() {
		Iterator i = nt.iterator();

		while(i.hasNext())
			System.out.println( (String) i.next());
	}

	/**
	 * Displays the list of rules
	 */
	public void printRules() {
		Enumeration e = rules.elements();

		while(e.hasMoreElements())
			System.out.println( e.nextElement());
	}

	/**
	 * Displays the set of items collections generated
	 */
	public void printCollectionOfSets() {
		Iterator i2;
		Enumeration e = setMapping.keys();
		HashSet s;
		int ctr=0;

		while(e.hasMoreElements()) {
			i2 = ( s=(HashSet) e.nextElement() ).iterator();
			System.out.println("Set " + setMapping.get(s));
			while(i2.hasNext()) {
				System.out.println(i2.next());
			}
		}
	}

	/**
	 * Displays the start symbol
	 */
	public void printStartSymbol() {
		System.out.println(startSymbol);
	}

	/**
	 * Determines if the terminal string passed exists in the terminal list
	 *
	 * @param s The terminal string
	 * @return True if the given terminal exists, false otherwise
	 */
	public boolean hasTerminal(String s) {
		return t.contains(s.toUpperCase());
	}

	/**
	 * Determines if the non-terminal string exists in the non-terminal list
	 *
	 * @param s Non-terminal string
	 * @return True is the given non-terminal exists, false otherwise
	 */
	public boolean hasNonTerminal(String s) {
		return nt.contains(s.toUpperCase());
	}

	/**
	 * Checks if the passed character is a delimiter
	 *
	 * @param c delimiter charater
	 * @return True if the passed character is a delimiter used by the generator
	 */
	protected boolean isDelim(char c) {
		for(int i=0;i<delims.length();i++)
			if(delims.charAt(i) == c)
				return true;
		return false;
	}

	/**
	 * Displays the contents of the hashset as a string
	 */
	static void printSet(HashSet s) {
		Iterator i = s.iterator();

		while(i.hasNext())
			System.out.println(i.next().toString());
	}

	void displaySetsOfItems() {
		Enumeration i = setMapping.keys();
		HashSet hs;
		int ctr = 0;

		while(i.hasMoreElements()) {
			hs = ((HashSet) i.nextElement());
			System.out.println( ((Integer)setMapping.get(hs)).intValue()+ ":");
			printSet( hs );
			ctr++;
		}
	}
}